#include "pila.h"
#include <stdio.h>
#include <stdbool.h>
#include "abb.h"
#include <stdlib.h>
#include <string.h>


typedef struct nodo{
	char* clave;
	void* dato;
	struct nodo *izq,*der;
}nodo_t;
struct abb{
	abb_comparar_clave_t fcmp;
	abb_destruir_dato_t fdestruir_dato;
	nodo_t* raiz;
	int cant;
};
struct abb_iter{
	pila_t* pilaiter;
};
typedef struct cont{
	int valor;
}cont_t;
cont_t* cont_crear(){
	cont_t* contador=malloc(sizeof(cont_t));
	if(!contador){
		free(contador);
		return NULL;}
	contador->valor=0;
	return contador;
}
//Pre:Se le pasa por parametro 2 funciones: la primera es la que compara
//las claves del arbol y la segunda la que destruye los datos, segun lo que almacene
//Post: si todo sale bien se devuelve un puntero a arbol vacio, si se produce 
//algun error se devuelve NULL
abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato){
	//Si no se envio la funcion para comparar claves o destruir datos, devuelvo NULL.
	if(!cmp)return NULL;
	
	abb_t* arbol=malloc(sizeof(nodo_t));
	if(!arbol)return NULL;
	
	//si esta todo bien inicializo funciones y valores y devuelto puntero al arbol
	arbol->fcmp=cmp;
	arbol->fdestruir_dato= destruir_dato;
	arbol->raiz=NULL;
	arbol->cant=0;
	return arbol;
}

//Pre: No se le pasan parametro
//Post: si todo sale bien se devuelve un puntero a nodo vacio, si se produce 
//algun error se devuelve NULL
nodo_t* nodo_crear(){
	//Si no se envio la funcion para comparar claves o destruir datos, devuelvo NULL.	
	nodo_t* arbol=malloc(sizeof(nodo_t));
	if(!arbol)return NULL;
	
	//si esta todo bien inicializo funciones y valores y devuelto puntero al arbol
	arbol->izq=NULL;
	arbol->der=NULL;
	arbol->dato=NULL;
	arbol->clave=NULL;

	return arbol;
}

//Pre: se le pasa un arbol y una clave del elemento a insertar
//Post: devuelve puntero a el ultimo nodo en que se deberia insertar(actualizar,
//hijo izq o hijo derecho) y actualiza nodopadre con un puntero al padre,
//devuelve NULL si hay algun error.
nodo_t* posinsertar(nodo_t* arbol,const char* clave,bool buscopadre,abb_comparar_clave_t fcmp,cont_t* contador){
	if((!arbol->clave)||(!arbol))return NULL;
	//comparo la clave con la porcion del arbol con la que estoy trabajando
	int comparacion=fcmp(arbol->clave,clave);
	nodo_t* arbolres;
	switch(comparacion){
		case 1:
			//busco la posicion en el subarbol izq
			if(arbol->izq==NULL)return arbol;
			arbolres=posinsertar(arbol->izq,clave,buscopadre,fcmp,contador);
			break;
		case 0:
			//devuelvo el nodo tal que lo tengo que actualizar
			return arbol;
			break;
		case -1:
			//busco posicion en el subarbol derecho
			if(arbol->der==NULL)return arbol;
			arbolres=posinsertar(arbol->der,clave,buscopadre,fcmp,contador);
			break;
	}
	if(contador){
		if((buscopadre)&&(contador->valor==0)){
			//cuando sale la primera vez de la recursividad, actualiza el
			//puntero a padre
			contador->valor++;
			return arbol;
		}
	}
	return arbolres;
}


//Pre: Se creo el arbol, se le pasa por parametro el arbol creado, la clave
// y el dato.
//Post: devuelve el true y actualiza el arbol si todo salio bien, devuleve fase
//si se produce algun error.
bool abb_guardar(abb_t *arbol, const char *clave, void *dato){
	if((!arbol)||(!clave)||(!dato))return false;
	//si no tiene raiz significa que estoy guardando en arbol vacio		
	if(!arbol->raiz){
		nodo_t* nodoraiz=nodo_crear();
		nodoraiz->dato=dato;
		nodoraiz->clave=malloc(sizeof(char*)*strlen(clave)+1);
		if(!nodoraiz->clave){
			free(nodoraiz);
			return false;
		}
		strcpy(nodoraiz->clave,clave);
		arbol->raiz=nodoraiz;
		arbol->cant++;
		return true;
	}

	//si hay raiz busco el nodo en que hay que insertar y veo en que parte lo debo insertar
	nodo_t* nodoinsert=posinsertar(arbol->raiz,clave,NULL,arbol->fcmp,NULL);
	
	int comparar=arbol->fcmp(nodoinsert->clave,clave);
	nodo_t* nuevonodo;
	if(comparar!=0){
		//inicializo subarbol si tengo que insertar nuevo
		nuevonodo= nodo_crear();
		nuevonodo->dato=dato;
		nuevonodo->clave=malloc(sizeof(char*)*strlen(clave)+1);
		if(!nuevonodo->clave){
			free(nuevonodo);
			return false;
		}
		strcpy(nuevonodo->clave,clave);
	}
	switch(comparar){
		case 1:
		//tiene que insertar a la izquierda
			arbol->cant++;
			nodoinsert->izq=nuevonodo;
			break;
		case 0:
		//tiene que actualizar el nodo
			if(arbol->fdestruir_dato)
				arbol->fdestruir_dato(nodoinsert->dato);
			nodoinsert->dato=dato;
			break;
		case -1:
		//tiene que insertar a la derecha
			arbol->cant++;
			nodoinsert->der=nuevonodo;
			break;
	}
	return true;
}

//Pre: se le pasa el arbol y la clave por parametro (ya creadas)
//Post: devuelve true si la clave pertenece al arbol, devuelve false si
//la clave no pertenece o no se le envio algun parametro.
bool abb_pertenece(const abb_t *arbol, const char *clave){
	if((!arbol)||(!arbol->raiz)||(!clave))return false;
	//busco la posicion donde lo deberia insertar
	cont_t* contador=cont_crear();
	if(!contador){
		free(contador);
		return NULL;}
	nodo_t* nodo=posinsertar((nodo_t*)arbol->raiz,clave,NULL,arbol->fcmp,contador);
	free(contador);
	//si esa posicion pertenece a la actualizacion entonces, pertenece,
	//sino no
	if(!nodo){
		//primer nodo vacio sin clave
		return false;
	}
	int comparar=arbol->fcmp(nodo->clave,clave);

	if(comparar!=0)return false;
	return true;
}

//Pre: se le pasa el nodo a borrar que tiene dos hijos no nulos
//Post: devuelve el nuevo nodo raiz del subarbol y actuliza la referencia 
//su padre
nodo_t* buscar_nuevo_nodo(nodo_t* arbol){
	if(!arbol)return NULL;
	nodo_t* nodores=NULL,* nodopadre=NULL;
	
	nodores=arbol->der;
	nodopadre=arbol;
	while(nodores->izq){
		nodopadre=nodores;
		nodores=nodores->izq;
	}		
	if(nodopadre==arbol){
		//si solo tiene un hijo derecho
		if(nodores->der){
			//si el nuevo nodo raiz tiene hijos mas grandes
			arbol->der=nodores->der;
		}else{
			//si no tiene hijos
			arbol->der=NULL;
		}
	}else{
		//si tiene muchos subarboles izquierdon luego del hijo derecho
		if(nodores->der){
			//si el nodo mas a la izquierda respecto a la derecha de la raiz
			//del arbol tiene hijo derecho
			nodopadre->izq=nodores->der;
			nodores->der=NULL;
		}else{
			//si no tiene hijo derecho
			nodopadre->izq=NULL;
		}
	}
	return nodores;
	
}

//Pre: se le pasa un arbol y una clave a borrar
//Post: devuelve el nodo y lo borra del arbol
nodo_t* actualizar_arbol(abb_t* arbol,const char* clave){
	//busco el padre del nodo a borrar
	cont_t* contador=cont_crear();
	if(!contador){
		free(contador);
		return NULL;}
	nodo_t* padre=posinsertar(arbol->raiz,(char*)clave,true,arbol->fcmp,contador);
	free(contador);
	//busco la posicion de nodo a borrar respecto al padre
	int comparacion=arbol->fcmp(padre->clave,clave);
	nodo_t* nodoborrar=NULL;

	if(comparacion == 1){
			//es el hijo izq
			//asigno el nodo a borrar
			nodoborrar=padre->izq;
			if((!nodoborrar->izq)&&(!nodoborrar->der)){
				//no tiene hijos
				padre->izq=NULL;
			}else if(!nodoborrar->izq){
				//tiene solo hijo der
				padre->izq=nodoborrar->der;	
				nodoborrar->der=NULL;
			}else if(!nodoborrar->der){
				//tiene solo hijo izq
				padre->izq=nodoborrar->izq;				
				nodoborrar->izq=NULL;

			}else{
				//tiene 2 hijos
				//nuevo nodo es el nodo que va a pasar a ser raiz
				nodo_t* nuevonodo=buscar_nuevo_nodo(nodoborrar);
				//asigno nuevos hijos a nuevo nodo
				nuevonodo->izq=nodoborrar->izq;
				nuevonodo->der=nodoborrar->der;
				//pongo en nulos los hijos del nodo a borrar
				nodoborrar->izq=NULL;
				nodoborrar->der=NULL;
				//actualizo el nuevo hijo izq del padre
				padre->izq=nuevonodo;		
			}
	}else if(comparacion == -1){
			//es el hijo der
			//asigno el nodo a borrar
			nodoborrar=padre->der;
			if((!nodoborrar->izq)&&(!nodoborrar->der)){
				//no tiene hijos
				padre->der=NULL;
			}else if(!nodoborrar->izq){
				//tiene solo hijo der
				padre->der=nodoborrar->der;	
				nodoborrar->der=NULL;
			}else if(!nodoborrar->der){
				//tiene solo hijo izq
				padre->der=nodoborrar->izq;				
				nodoborrar->izq=NULL;
			}else{
				//tiene 2 hijos
				//nuevo nodo es el nodo que va a pasar a ser raiz
				nodo_t* nuevonodo=buscar_nuevo_nodo(nodoborrar);
				//asigno nuevos hijos a nuevo nodo
				nuevonodo->izq=nodoborrar->izq;
				nuevonodo->der=nodoborrar->der;
				//pongo en nulos los hijos del nodo a borrar
				nodoborrar->izq=NULL;
				nodoborrar->der=NULL;
				//actualizo el nuevo hijo izq del padre
				padre->der=nuevonodo;
			}
	}else{
		//borro la raiz del arbol
		nodoborrar=arbol->raiz;
		if((!arbol->raiz->izq)&&(!arbol->raiz->der)){
			arbol->raiz=NULL;
		}else if(!arbol->raiz->izq){
			//solo tiene subarbol derecho
			arbol->raiz=nodoborrar->der;
			nodoborrar->der=NULL;
		}else if(!arbol->raiz->der){
			//solo tiene subarbol izquierdo
			arbol->raiz=nodoborrar->izq;
			nodoborrar->izq=NULL;
		}else{
			//tiene 2 hijos
			//nuevo nodo es el nodo que va a pasar a ser raiz
			nodo_t* nuevonodo=buscar_nuevo_nodo(nodoborrar);
			//asigno nuevos hijos a nuevo nodo
			nuevonodo->izq=nodoborrar->izq;
			nuevonodo->der=nodoborrar->der;
			arbol->raiz=nuevonodo;
			//pongo en nulos los hijos del nodo a borrar
			nodoborrar->izq=NULL;
			nodoborrar->der=NULL;			
		}
	}
    return nodoborrar;
}
//Pre: se le pasa un arbol(cada nodo tiene clave y dato),una funcion de 
//tipo void que se le pasa por parametro un puntero a memoria.
//Post: la funcion itero el arbol de modo in order y aplico la funcion
//pasada por parametro a cada nodo. No devuelve valor.
void void_abb_in_order(nodo_t *arbol, void funcion(void *),bool nodo){
	//si no se mando el arbol o la funcion se produce error	
	if ((!arbol)||(!funcion)) return;
	//Me copio el subarbol derecho para que una vez liberado no se
	//pierda la referencia
	nodo_t* arbder= arbol->der;
	void_abb_in_order(arbol->izq,funcion,nodo);
	if(nodo){
		//destruyo la clave y el nodo
		funcion(arbol->clave);
		funcion(arbol);
	}else{
		//destruyo el dato
		funcion(arbol->dato);	
	}
	void_abb_in_order(arbder,funcion,nodo);
	return;
}

//Pre: se le pasa un arbol por parametro
//Post: destruye todo el arbol, incluyendo subarboles, destruye tanto  
//los nodos como los datos
void subarbol_destruir(nodo_t *arbol,abb_destruir_dato_t fdestruir_dato ){
	if(!arbol)return;
	if(fdestruir_dato!=NULL)
		void_abb_in_order(arbol,fdestruir_dato,false);
	void_abb_in_order(arbol,free,true);	
	return;
}

//Pre:Se le pasa un arbol y una clave a borrar
//Post: Si la clave y el arbol existen devuelve el dato asociado a la 
//misma, sino devuelve NULL
void *abb_borrar(abb_t *arbol, const char *clave){
	//si no esta devuelvo NULL	
	if((!arbol)||(!abb_pertenece(arbol,clave)))
		return NULL;

	nodo_t* nodoborrar=actualizar_arbol(arbol,clave);
	void* dato=nodoborrar->dato;
	subarbol_destruir(nodoborrar,arbol->fdestruir_dato);
	arbol->cant--;
	return dato;			

}

//Pre: se le pasa un nodo(cada nodo tiene clave y dato),una funcion booleana
// y un extra a la funcion
//Post: la funcion itero el arbol de modo in order y aplico la funcion
//pasada por parametro a cada nodo. No devuelve valor.
void abb_in_order_aux(nodo_t *arbol, bool funcion(const char *, void *, void *), void *extra){
	abb_in_order_aux(arbol->izq,funcion,extra);
	funcion(arbol->clave,arbol->dato,extra);
	abb_in_order_aux(arbol->der,funcion,extra);
	return;
}
//Pre: se le pasa un arbol(cada nodo tiene clave y dato),una funcion booleana
// y un extra a la funcion
//Post: la funcion itero el arbol de modo in order y aplico la funcion
//pasada por parametro a cada nodo. No devuelve valor.
void abb_in_order(abb_t *arbol, bool funcion(const char *, void *, void *), void *extra){
	//si no se mando el arbol o la funcion se produce error	
	if ((!arbol)||(!funcion)) return;
	abb_in_order_aux(arbol->raiz,funcion,extra);
	return;
}


//Pre: se le pasa un arbol por parametro
//Post: destruye todo el arbol, incluyendo subarboles, destruye tanto  
//los nodos como los datos
void abb_destruir(abb_t *arbol){
	if(!arbol)return;
	subarbol_destruir(arbol->raiz,arbol->fdestruir_dato);
	free(arbol);
	return;
}

//Pre: se le pasa un arbol por parametro
//Post: devuelve la cantidad de nodos del arbol
size_t abb_cantidad(abb_t* arbol){
	if(!arbol)return 0;
	return arbol->cant;
}


//Pre: se le pasa una arbol ya creado y una clave por parametro
//Post: si no se le manda un parametro o la clave no existe devuelve NULL
//si todo sale bien devuelve el dato correspondiente a esa clave
void *abb_obtener(const abb_t *arbol, const char *clave){
	if((!arbol)||(!arbol->raiz)||(!clave)) return NULL;
	cont_t* contador=cont_crear();
	if(!contador){
		free(contador);
		return NULL;}
	nodo_t* busqueda=posinsertar((nodo_t*)arbol->raiz, (char*)clave,NULL,arbol->fcmp,contador);
	free(contador);
	if(!busqueda)return NULL;

	int comparar=arbol->fcmp(busqueda->clave,clave);
	if(comparar!=0)return NULL;
	return busqueda->dato;
}	

//Pre: se le pasa un arbol por parametro
//Post: devuelve un iter parado en la primer posicion del arbol
//(con clave mas baja) si hay un error con memoria devuelve NULL
abb_iter_t *abb_iter_in_crear(const abb_t *arbol){
	abb_iter_t* iter= malloc(sizeof(abb_iter_t));
	if (!iter)return NULL;
	iter->pilaiter=pila_crear();
	if(!iter->pilaiter){
		free(iter);
		return NULL;
	}
	
	//si no hay nada para apilar, devuelvo iter de arbol vacio.
	if(!arbol->raiz) return iter;
	nodo_t* actual= (nodo_t*)arbol->raiz;
	bool control=true;
	//apilo raiz
	control=pila_apilar(iter->pilaiter,actual);

	while(actual->izq){
		//apilo hijos izquierdos
		if (!control)return NULL;
		control=pila_apilar(iter->pilaiter,actual->izq);
		actual=actual->izq;
	}
	return iter;
}

//Pre:se le pasa el iter por parametro
//Post: devuelve true si pudo avanzar de modo inorder, false se produjo
//algun error
bool abb_iter_in_avanzar(abb_iter_t *iter){
	//si no le mando el iter devuelvo false
	if(!iter)return false;
	
	//valido que la pila tenga algo
	if(pila_esta_vacia(iter->pilaiter))	return false;
	
	//desapilo el actual
	nodo_t* actual=pila_desapilar(iter->pilaiter);
	if(actual){
		bool control=true;
		if(actual->der){
			 control=pila_apilar(iter->pilaiter,actual->der);
			actual=actual->der;
			if(!control)
				return false;	
		
			//apilo todos los hijos izq
			while(actual->izq){

				control=pila_apilar(iter->pilaiter,actual->izq);
				actual=actual->izq;
				if(!control)
					return false;	
			}	
		}
	}
	return true;
}
//Pre: se le pasa el iter al final
//Post: devuevle la clave si esta parado en un nodo,
//devuelve NULL si esta al finl o se produjo algun error
const char *abb_iter_in_ver_actual(const abb_iter_t *iter){
	if((!iter)||(!iter->pilaiter))return NULL;
	if(pila_esta_vacia(iter->pilaiter))return NULL;
	char* resultado=((nodo_t*)pila_ver_tope(iter->pilaiter))->dato;
	return resultado;
}
//Pre: se le pasa el iter por parametro
//Post:devuelve true si esta al final, devuelve false si no esta al final
//o se produjo algun error
bool abb_iter_in_al_final(const abb_iter_t *iter){
	if(!iter)return false;
	nodo_t* nodo= pila_ver_tope(iter->pilaiter);

	if(!nodo)return true;
	return false;
}
//Pre: se le pasa el iter por paremtro
//Post: libero el espacio asignado al iter en memoria
void abb_iter_in_destruir(abb_iter_t* iter){
	if (!iter)return;
	
	//destruyo pila
	pila_destruir(iter->pilaiter);
	//destruyo iter
	free(iter);
	return;
}

